package shu;

import java.util.Stack;

public class Traverse {
    //先序
    public static void preOrder(BiTreeNode root){
        if (root!=null){
            System.out.print(root.data);//先访问根节点
            preOrder(root.lchild);//先序遍历左子树
            preOrder(root.rchild);//先序遍历右子树
        }
    }
    //中序
    public static void inOrder(BiTreeNode root){
        if (root!=null){
            inOrder(root.lchild);//先序遍历左子树
            System.out.print(root.data);//先访问根节点
            inOrder(root.rchild);//先序遍历右子树
        }
    }

    //后序
    public static void outOrder(BiTreeNode root){
        if (root!=null){
            outOrder(root.lchild);//先序遍历左子树
            outOrder(root.rchild);//先序遍历右子树
            System.out.print(root.data);//先访问根节点
        }
    }
    //非递归，用栈实现
    public  static void preOrder2(BiTreeNode root){
        Stack<BiTreeNode> stack = new Stack<>();
        if(root==null){
            return;

        }
        stack.push(root);//根先进栈
        BiTreeNode current;
       while(!stack.isEmpty()){
           current=stack.pop();
           System.out.println(current.data);
            //栈顶的右孩子左孩子依次进栈
           if(current.rchild!=null){
               stack.push(current.rchild);
           }
           if(current.lchild!=null){
               stack.push(current.lchild);
           }

       }
    }

}
